package jianzhi_offer;

import java.util.ArrayList;
import java.util.Set;
import java.util.TreeSet;

public class _23_二叉树中和为某一值的路径 {
	Set<ArrayList<Integer>> set = new TreeSet<ArrayList<Integer>>((o1,o2)->o2.size()-o1.size());
	public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        dfs(root,0,target,new ArrayList<Integer>());
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(set);
        return res;
    }
	
	public void dfs(TreeNode root,int sum,int target,ArrayList<Integer> list) {
		if(root == null) {
			if(sum == target && list.size() != 0) {
				ArrayList<Integer> temp = new ArrayList<Integer>(list);
				set.add(temp);
			}
			return ;
		}
		list.add(root.val);
		dfs(root.left,sum+root.val,target,list);
		dfs(root.right,sum+root.val,target,list);
		list.remove(list.size()-1);//回溯
	}
}
